package h0902;

import java.util.ArrayList;
import java.util.List;

public class RestoreIPAddresses {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return result;
        }
        backtrack(result, new StringBuilder(), s, 0, 0);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder current, String s, int index, int segment) {
        if (segment == 4 && index == s.length()) {
            result.add(current.toString());
            return;
        } else if (segment == 4 || index == s.length()) {
            return;
        }

        for (int len = 1; len <= 3; len++) {
            if (index + len > s.length()) break;

            String part = s.substring(index, index + len);
            if ((part.startsWith("0") && part.length() > 1) || Integer.parseInt(part) > 255) continue;

            int originalLength = current.length();
            if (segment > 0) current.append('.');
            current.append(part);

            backtrack(result, current, s, index + len, segment + 1);

            current.setLength(originalLength);
        }
    }

    public static void main(String[] args) {
        RestoreIPAddresses solution = new RestoreIPAddresses();
        String input = "25525511135";
        List<String> validIPs = solution.restoreIpAddresses(input);
        
        System.out.println("Valid IP addresses: ");
        for (String ip : validIPs) {
            System.out.println(ip);
        }
    }
}
